package com.ting.test.algorithms.大厂刷题班;

/**
 * 给定一个数组arr
 * 返回如果排序之后相邻两个数的最大差值
 * 思路 利用桶排序的思想
 * 假设有n个 数 那么分配n+1个桶
 * 利用桶排序 可以实现排序
 * 此时必然有一个桶是空的
 * 那么不同的桶直接的差一定大于同一个桶内的差
 */
public class 相邻两个数最大的差值 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 6, 8, 18, 2};
        int cha = process(arr);
        System.out.printf(cha+"");
    }

    private static int process(int[] arr) {
        if (null == arr || arr.length == 1) {
            return 0;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        //首先求出最大值和最小值，依此来确定范围
        for (int num : arr) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        int N = arr.length;
        boolean[] hasValues = new boolean[N + 1];//准备n+1个桶 默认false 表示桶都是空的
        int[] maxarr = new int[N + 1];//桶的最大值的
        int[] minarr = new int[N + 1];//桶的最小值的

        // 注意 每个桶只记录最大值和最小值,其余的直接抛弃
        for (int i = 0; i < arr.length; i++) {
            int index = getBucket(min, max, arr[i],N);
            hasValues[index] = true;
            maxarr[index] = hasValues[index] ? Math.max(maxarr[index], arr[i]) : arr[i];
            minarr[index] = hasValues[index] ? Math.min(minarr[index], arr[i]) : arr[i];
        }

        int  result=0;
        int preMax=maxarr[0];//上一个桶的最大值
        for(int i=1;i<hasValues.length;i++){
            if(hasValues[i]){
                result=Math.max(result,maxarr[i]-preMax);//当前桶的最大值减去上一个桶的最小值，可以得到一个相对的最大值
                preMax=maxarr[i];
            }

        }

        return result;
    }

    private static int getBucket(int min, int max, int num,int len) {
        int rand = max - min;
       return (num-min)*len/rand;
    }
}
